package cn.edu.cdu.argorithm.impl;

import cn.edu.cdu.argorithm.ILinkedListCycle;
import cn.edu.cdu.argorithm.common.ListNode;

import java.util.HashSet;
import java.util.Set;

public class LinkedListCycleSolutions {
    public static class Solution1 implements ILinkedListCycle {
        @Override
        public boolean hasCycle(ListNode head) {
            Set<ListNode> cache = new HashSet<>();
            while (head != null) {
                if(!cache.add(head)) {
                    return true;
                }
                head = head.next;
            }
            return false;
        }
    }

    public static class Solution2 implements ILinkedListCycle {
        @Override
        public boolean hasCycle(ListNode head) {
            if(head == null || head.next == null){
                return false;
            }
            ListNode slow = head, fast = head.next;
            while (slow != fast && fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow == fast;
        }
    }
}
